package com.acwing.partition6;

import java.io.*;

/**
 * @author `RKC`
 * @date 2022/3/22 14:55
 */
public class AC587吃蛋糕 {

    private static final int N = 10010, INF = 0x3f3f3f3f;
    private static int[] f = new int[N];
    private static int n;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int t = Integer.parseInt(reader.readLine());
        for (int k = 1; k <= t; k++) {
            n = Integer.parseInt(reader.readLine());
            for (int i = 0; i <= n; i++) f[i] = INF;
            for (int i = 0; i * i <= n; i++) f[i * i] = 1;
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j * j <= i; j++) {
                    f[i] = Math.min(f[i], f[i - j * j] + f[j * j]);
                }
            }
            writer.write(String.format("Case #%d: %d\n", k, f[n]));
        }
        writer.flush();
    }
}
